/*
 * Copyright (c) 2008, Justin Choy
 * All rights reserved.
 * 
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are met:
 * 
 * 1) Redistributions of source code must retain the above copyright notice, 
 * this list of conditions and the following disclaimer.
 * 
 * 2) Redistributions in binary form must reproduce the above copyright notice, 
 * this list of conditions and the following disclaimer in the documentation 
 * and/or other materials provided with the distribution.
 * 
 * 3) Neither the name of the owner nor the names of its contributors may 
 * be used to endorse or promote products derived from this software without 
 * specific prior written permission.
 * 
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS IS" 
 * AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE 
 * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE 
 * ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE 
 * LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR 
 * CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF 
 * SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS 
 * INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN 
 * CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) 
 * ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE 
 * POSSIBILITY OF SUCH DAMAGE.
 */
package algorithms;

import data.Array;
import error.OutOfMemoryException;
import error.ProgrammingErrorException;

/**
 * An example of using the Insertion sort Algorithm
 * The insertion sort inserts values into the correct place in a sorted array
 * by shifting all other values to make space for it. We start with a sorted
 * array of size 1 element and insert the index=1 element correctly (i.e: we
 * swap or no swap). So on and so forth till we get to the last element.
 * 
 * O(N^2)
 * 
 * @author jchoy
 */
public class InsertionSort {
    public InsertionSort() {
    }

    /**
     * @param args
     */
    public static void main(String[] args) {
        try {
            InsertionSort.InsertionSortedArray array 
                = new InsertionSort().new InsertionSortedArray();
            
            System.out.println( "Filling Array...");
            array.fillWithRandomNumbers(50000);
            
            System.out.println( "Insertion Sorting..." );
            
            long startTime = System.currentTimeMillis();
            array.sort();
            long stopTime = System.currentTimeMillis();
            long sortTime = stopTime - startTime;
            
            System.out.println( "It took " + Long.toString(sortTime) + "ms");
            
            System.out.print( "Testing sort...");
            
            if ( array.isOrdered() == true) {
                System.out.println( "PASS!" );
            } else {
                System.out.println( "FAIL!" );
            }
            
        } catch (ProgrammingErrorException e) {
            System.out.println( e.getMessage() );
        } catch (OutOfMemoryException e) {
            System.out.println(e.getMessage());
        }
    }
    
    
    class InsertionSortedArray extends Array {
        public InsertionSortedArray() {
        }
        
        /**
         * Sorts the array using insertion sort.
         * 
         * @throws ProgrammingErrorException 
         */
        public void sort() throws ProgrammingErrorException {
            long tempValue = -1;
            int curIndex  = -1;
            int stop = 0;

            /* Start with a two element sub-array and increase the size by
             * 1 every time. 
             */
            for ( stop = 1; stop < getNumElements(); stop++ ) {
                
                /* Extract the stop element */
                tempValue = array[stop];
                curIndex = stop;
                
                /* Shift all elements that are greater than the stopElement
                 * to the right until the stopElement is greater than the
                 * current element
                 */
                while (curIndex > 0 && array[curIndex - 1] >= tempValue) {
                    array[curIndex] = array[curIndex - 1];
                    curIndex--;
                }
                array[curIndex] = tempValue;
            }
        }
    }
    
    

}
